/*
  Grupo 2
  
  Luiz Felipe de Souza Mattos 	RA 107822
  
  Debora Maia Silva 	      	RA 101985

*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hash.h" 

/* cria um vetor do hash com tamanho passado */
void CriaHash(Hash **vet,int tamanho)
{
	*vet = (Hash *)malloc(tamanho * sizeof(Hash));
	return;
}

/* inicializa as informacoes do hash */
void inicializaHash(Hash *vet)
{
	int i;
	
	for(i=0; i<13; i++)
	{
		vet[i].tamanho = 0;
		vet[i].lista = NULL;
	}
}

/* funcao hash utilizada, algoritmo fornecido pelo enunciado */
int funcHash(char *nome)
{
	int vet[50];
	int tam, i;
	
	tam = (int)strlen(nome);
	
	for(i=0; i<tam; i++)
	{
		if (nome[i] >= 0)
			vet[i] = nome[i];
		else
			vet[i] = 256 + nome[i];
	}

	for(i=1; i<tam; i++)
		vet[0] ^= vet[i];
	
	return vet[0]%13;
}

/* procura nome na lista de aluno */
int buscaLista(char *nome, Aluno **inicio)
{
	Aluno *aux;
	int res = 0;
	
	aux = *inicio;
	
	while(aux != NULL)
	{
		if(strcmp(aux->nome, nome) == 0)
		{
			res = 1;
			break;
		}
		aux = aux->prox;
	}
	
	return res;
}

/* procura nome igual no hash */
int buscaIgual(char *nome, Hash *vet, int posicao)
{
	int res;
	
	if (vet[posicao].tamanho == 0) /* posicao vazia, nao ha igual */
		return 0;
	
	else /* tem alguem nos buckets da posicao, deve-se checar se nao ha nome igual */ 
	{
		res = buscaLista(nome, &vet[posicao].lista);
		return res;
	}
}

/* procura a posicao certa para inserir o registro na lista da posicao ja calculada
do hash */
void insereHash(Aluno **novo, Aluno **lista)
{
	Aluno *aux1, *aux2;
	
	
	if(*lista == NULL) /* insere primeiro elemento */
	{
		*lista = *novo;
		(*novo)->prox = NULL;
	}
	
	else
	{
		aux1 = *lista;

		if(strcmp(aux1->nome, (*novo)->nome) > 0) /* inserir no comeco */
		{
			(*novo)->prox = *lista;
			*lista = *novo;
		}
		else /* procura posicao correta a inserir */
		{
			aux2 = *lista;
				
			/* a posicao correta eh apos aux2 */
			while(aux2->prox != NULL && strcmp(aux2->prox->nome, (*novo)->nome) < 0) /* enquanto tiver proximo e o a inserir for maior */
				aux2 = aux2->prox;
				
			if(aux2->prox == NULL) /* inserir no final */
			{
				aux2->prox = *novo;
				(*novo)->prox = NULL;
			}
				
			else /* inserir entre dois elementos, entre aux2 e aux2->prox */
			{
				(*novo)->prox = aux2->prox;
				aux2->prox = (*novo);
			}
		}
	}
}

void insereAluno(Aluno *aluno, Hash *vet)
{
	int posicao, repetido;
	Aluno *novo;
	
	/* busca posicao hash de acordo com a funcao do enunciado */
	posicao = funcHash(aluno->nome);
	
	/* verifica se nao ha registro com nome igual */
	repetido = buscaIgual(aluno->nome, vet, posicao);
	
	if(repetido)
	{
		printf("Insere: %06d \"%s\"\n", aluno->ra, aluno->nome);
		printf("Nome repetido: ");
		printf("\"%s\"", aluno->nome);
		printf("\n");
	}
	else /* nao eh repetido, deve-se inserir no hash */
	{
		novo = (Aluno *)malloc(sizeof(Aluno));
		novo->nome = aluno->nome;
		aluno->nome = NULL;
		novo->ra = aluno->ra;
		insereHash(&novo, &vet[posicao].lista);
		vet[posicao].tamanho++;
		printf("Insere: %06d \"%s\"", novo->ra, novo->nome);
		printf("\n");
	}
}

/* conta o tamanho de cada posicao do hash */
int contaAlunos(Hash *vet)
{
	int total = 0, i;
	
	for(i=0; i<13; i++)
		total += vet[i].tamanho;
	
	return total;
}

/* imprime uma lista ligada de uma posicao do hash */
void imprimeBucket(int posicao, Aluno *lista)
{
	Aluno *aux;
	
	/* nao precisa checar se eh diferente de NULL pq jah foi testado isso em tamanho != 0 */
	
	aux = lista;

	while(aux != NULL)
	{
		printf("(%d) %06d \"%s\"", posicao, aux->ra,aux->nome);
		printf("\n");
		aux = aux->prox;
	}
}

/* imprime todos os registros do hash */
void imprime(Hash *vet,int tamanho)
{
	int numeroAlunos, i;
	
	numeroAlunos = contaAlunos(vet);
	
	printf("\nImprime Tabela: %d aluno(s):\n", numeroAlunos);
	
	for(i=0; i<tamanho; i++)
	{
		if(vet[i].tamanho != 0) /* se ha alunos no bucket */
			imprimeBucket(i,vet[i].lista);
	}
	printf("\n");
}

/* libera a memoria usada pela lista dos registros */
void LiberaLista(Aluno **lista)
{
	Aluno *aux;

	aux = *lista;

	while (aux != NULL)
	{
		*lista = aux->prox;
		free(aux->nome);
		free(aux);
		aux = NULL;
		aux = *lista;
	}
}

/* libera toda memoria usada pelo hash */
void LiberaHash(Hash *vet)
{
	int i;

	for (i = 0;i < 13;i++)
	{
			LiberaLista(&vet[i].lista);
	}
	/* libera o vetor do hash */
	free(vet);
}

/* retira nome da lista */
void retiraLista(char *nome, Aluno **lista)
{
	Aluno *aux1, *aux2;
	
	aux1 = *lista;
	
	if(strcmp(aux1->nome, nome) == 0) /* eh o primeiro a ser removido */
	{
		*lista = aux1->prox; /* se for o unico, fica NULL */
		free(aux1->nome);
		free(aux1);
	}
	
	else /* nao eh o primeiro, deve-se procurar o correto para remover */
	{
		while(aux1!= NULL)
		{
			if(strcmp(aux1->nome, nome) == 0)
			{
				aux2 = *lista;
				
				while(aux2->prox != aux1)
					aux2 = aux2->prox;
				
				aux2->prox = aux1->prox;
				free(aux1->nome);
				free(aux1);
				
				break; /* jah removeu, nao precisa ficar procurando mais */
			}
			
			aux1 = aux1->prox;
		}
	}

}

/* busca um aluno por nome e remove do hash */
void removeAluno (char *nome, Hash *vet)
{
	int posicao, existe;

	/* busca posicao hash de acordo com a funcao do enunciado */
	posicao = funcHash(nome);
	
	/* checa se jah existe aluno com esse nome */
	existe = buscaIgual(nome, vet, posicao);
	
	if(!existe) /* caso nao tenha o que remover */
	{
		printf("Remove: \"%s\"\n",nome);
		printf("Nome inexistente: \"%s\"\n",nome);	
	}
	
	else /* o nome exite no hash e deve ser removido */
	{
		vet[posicao].tamanho--;
		retiraLista(nome, &vet[posicao].lista);
		printf("Remove: \"%s\"\n",nome);
	}
}

/* busca um nome de aluno e retorna o ponteiro para o registro */
Aluno* buscaAluno(char *nome, Aluno **lista)
{
	Aluno *aux;
	
	aux = *lista;
	
	while(aux != NULL)
	{
		if(strcmp(aux->nome, nome) == 0)
			return aux;
		
		aux = aux->prox;
	}
	return aux;
}

/* busca o aluno por nome e imprime o registro caso exista, e avisa caso nao exista */
void consultaAluno(char *nome, Hash *vet)
{
	int posicao, existe;
	Aluno *alunoAux;

	/* busca posicao hash de acordo com a funcao do enunciado */
	posicao = funcHash(nome);
	
	/* checa se jah existe aluno com esse nome */
	existe = buscaIgual(nome, vet, posicao);
	
	if(!existe) /* caso nao tenha o que consultar */
	{
		printf("Consulta: \"%s\"\n",nome);
		printf("Nome inexistente: \"%s\"\n",nome);	
	}
	
	else /* o nome exite no hash e deve-se imprimir informacoes de consulta */
	{
		alunoAux = buscaAluno(nome, &vet[posicao].lista);
		printf("Consulta: \"%s\"\n",nome);
		printf("%06d \"%s\"\n", alunoAux->ra, alunoAux->nome);
	}
	
}
